#+TITLE: The Seasoned Schemer Notes
#+SUBTITLE: Chapter 13
#+AUTHOR: Zelphir Kaltstahl
#+DATE: [2023-02-26 So]
#+LANGUAGE: English
#+TAGS: Scheme, The Seasoned Schemer
#+CREATOR: Emacs
#+EXCLUDE_TAGS: noexport
#+OPTIONS: ^:{} H:10 toc:3
#+STARTUP: content indent align inlineimages hideblocks entitiesplain nologdone nologreschedule nologredeadline nologrefile

* Prerequisites
:PROPERTIES:
:CUSTOM_ID: prerequisites
:END:


#+NAME: defatom
#+BEGIN_SRC scheme :noweb strip-export :results none :exports code :eval never-export
(define atom?
  (λ (x)
    (and (not (pair? x))
         (not (null? x)))))
#+end_src

In theory we could define other things as numbers, for example church numerals.

#+NAME: defonep
#+BEGIN_SRC scheme :noweb strip-export :results none :exports code :eval never-export
(define one?
  (λ (x)
    (= x 1)))
#+end_src

#+NAME: defpick
#+BEGIN_SRC scheme :noweb strip-export :results none :exports code :eval never-export
(define pick
  (λ (n lat)
    (cond
     [(one? n) (car lat)]
     [else
      (pick (- n 1) (cdr lat))])))
#+end_src

** Y-combinator
:PROPERTIES:
:CUSTOM_ID: prerequisites-y-combinator
:END:

In the first book the Y-combinator was derived. It is again:

#+NAME: y-combinator-def
#+begin_src scheme :noweb strip-export :results none :exports code :eval never-export :language guile
(define Y
  (λ (proc)
    ((λ (f) (f f))
     (λ (f)
       (proc
        (λ (x) ((f f) x)))))))
#+end_src

** All prerequisites                                              :noexport:
:PROPERTIES:
:CUSTOM_ID: prerequisites-all
:END:

#+NAME: prereq
#+BEGIN_SRC scheme :noweb strip-export :results none :exports none :eval never-export
<<defatom>>

<<defonep>>

<<defpick>>

<<y-combinator-def>>
#+END_SRC

* Chapter 13
:PROPERTIES:
:CUSTOM_ID: chapter-13
:END:

Chapter 13 deals with continuations. It shows situations, in which they can be useful. Situations, which before were not encountered. A typical situation is a recursive function, that builds up a result in recursive calls, but only after having potentially built up part of the result, notices that previously built up parts are not needed. This makes sense, when the check for some condition, that tells, that the parts are not needed is too expensive to be done in the average case.

** Example :: Computing the intersection of multiple sets
:PROPERTIES:
:CUSTOM_ID: chapter-13-example
:END:

One example the book uses is a function which computes the set intersection between multiple sets, represented by lists, given as a list of lists.

#+NAME: intersect-def
#+begin_src scheme :noweb strip-export :results output replace drawer :wrap example :exports code :eval never-export :language guile
(define intersect
  (λ (set1 set2)
    (letrec ([member?
              (λ (elem lst)
                (member elem lst))]
             [intersect-inner
              (λ (set1°)
                (cond
                 [(null? set1°) '()]
                 [(member? (car set1°) set2)
                  (cons (car set1°)
                        (intersect-inner (cdr set1°)))]
                 [else
                  (intersect-inner (cdr set1°))]))])
      (intersect-inner set1))))
#+end_src

#+NAME: intersectall-def-1
#+begin_src scheme :noweb strip-export :results output replace drawer :wrap example :exports code :eval never-export :language guile
<<intersect-def>>
(define intersectall
  (λ (lsts)
    (letrec ([intersectall-inner
              (λ (lsts°)
                (cond
                 [(null? (cdr lsts°)) (car lsts°)]
                 [else
                  (intersect (car lsts°)
                             (intersectall-inner (cdr lsts°)))]))])
      (cond
       [(null? lsts) '()]
       [else
        (intersectall-inner lsts)]))))
#+end_src

*** Usage
:PROPERTIES:
:CUSTOM_ID: chapter-13-example-usage
:END:

#+NAME: intersectall-usage-1
#+begin_src scheme :noweb strip-export :results output replace drawer :wrap example :exports both :eval never-export :language guile
<<intersectall-def-1>>
(simple-format
 #t "~a\n"
 (intersect '(a b c) '(c d e)))


(simple-format
 #t "~a\n"
 (intersectall '((a b c)
                 (c d e)
                 (f c))))

(simple-format
 #t "~a\n"
 (intersectall '((a b c)
                 (c d e)
                 ()
                 (f g c))))
#+end_src

#+RESULTS: intersectall-usage-1
#+begin_example
(c)
(c)
()
#+end_example

*** Conclusion
:PROPERTIES:
:CUSTOM_ID: chapter-13-example-conclusion
:END:

The problem with this definition of ~intersectall~ is, that even if a list in the call:

#+NAME: intersectall-recursive-call
#+begin_src scheme :noweb strip-export :results output replace drawer :wrap example :exports code :eval never-export :language guile
...
(intersect (car lsts°)
           (intersectall-inner (cdr lsts°)))
...
#+end_src

in ~intersectall-inner~ is empty, ~intersectall-inner~ in its iterations continues to call ~intersect~ with that empty list as a first argument. Continuing to call ~intersect~ is unnecessary work. Any intersection with an empty set will result in an empty set, in this case represented by an empty list. Any in previous iterations already computed partial intersection is useless as well. In fact the longer the already computed intersection is, the more work ~intersect~ will perform, because it iterates over the set members, checking, whether they are ~member?~ of the other set.

Ideally, even though the result computed by ~intersectall~ is correct, one would want to avoid this extra work being performed.

However, since the unnecessary expense of the computation is not noticed by any conditional in the code, it is not avoided.

*** Attempt of fixing the issue
:PROPERTIES:
:CUSTOM_ID: chapter-13-example-attempt-fix
:END:

It is also not simple to rewrite ~intersectall-inner~ to perform such a check. For example the following does not eliminate all redundant work:

#+NAME: intersectall-def-2
#+begin_src scheme :noweb strip-export :results output replace drawer :wrap example :exports code :eval never-export :language guile
<<intersect-def>>
(define intersectall
  (λ (lsts)
    (letrec ([intersectall-inner
              (λ (lsts°)
                (cond
                 [(null? (car lsts°)) '()]  ; added check
                 [(null? (cdr lsts°)) (car lsts°)]
                 [else
                  (intersect (car lsts°)
                             (intersectall-inner (cdr lsts°)))]))])
      (cond
       [(null? lsts) '()]
       [else
        (intersectall-inner lsts)]))))
#+end_src

Why does this not eliminate all redundant work? Because the return value of the check src_scheme[:exports code]{[(null? (car lsts°)) '()]}, the empty list, will still be used as an argument in calls of ~intersect~ in the ~else~ branch of the ~cond~ in earlier iterations of ~intersectall-inner~. Ideally one would avoid even calling ~intersect~ with any empty lists resulting from calls to ~intersectall-inner~.

*** Continuations to the rescue
:PROPERTIES:
:CUSTOM_ID: chapter-13-example-continuations
:END:

Fortunately, there is a good way to do so! Enter continuations.

We can store a continuation of the program before ~intersectall-inner~ is ever called. That continuation takes an argument, which is the result of ~intersectall-inner~. This way the continuation acts as means to do an early exit, no matter where the execution of ~intersectall-inner~ is, when it notices, that there is an empty list as return value of an ~intersectall-inner~ call. This is called an exit[fn:: or "escape"?] continuation.

#+NAME: intersectall-def-3
#+begin_src scheme :noweb strip-export :results output replace drawer :wrap example :exports code :eval never-export :language guile
<<intersect-def>>
(define intersectall
  (λ (lsts)
    (call-with-current-continuation
     (λ (exit)
       (letrec ([intersectall-inner
                 (λ (lsts°)
                   (cond
                    [(null? (car lsts°)) (exit '())]  ; exit continuation call
                    [(null? (cdr lsts°)) (car lsts°)]
                    [else
                     (intersect (car lsts°)
                                (intersectall-inner (cdr lsts°)))]))])
         (cond
          [(null? lsts) '()]
          [else
           (intersectall-inner lsts)]))))))
#+end_src

~intersectall-inner~ can be used just like before.

#+NAME: intersectall-usage-3
#+begin_src scheme :noweb strip-export :results output replace drawer :wrap example :exports both :eval never-export :language guile
<<intersectall-def-3>>
(simple-format
 #t "~a\n"
 (intersect '(a b c) '(c d e)))


(simple-format
 #t "~a\n"
 (intersectall '((a b c)
                 (c d e)
                 (f c))))

(simple-format
 #t "~a\n"
 (intersectall '((a b c)
                 (c d e)
                 ()
                 (f g c))))
#+end_src

#+RESULTS: intersectall-usage-3
#+begin_example
(c)
(c)
()
#+end_example

*** Further optimization of src_scheme[:exports code]{intersect} and src_scheme[:exports code]{intersectall}
:PROPERTIES:
:CUSTOM_ID: chapter-13-example-optimizations
:END:

However, there is still an issue with the definition of src_scheme[:exports code]{intersect} as defined above:

#+begin_src scheme :noweb yes :results output replace drawer :wrap example :exports code :eval never-export :language guile
<<intersect-def>>
#+end_src

When src_scheme[:exports code]{intersect} receives an empty list as a second argument. src_scheme[:exports code]{intersect-inner} will still go through all of the elements of the first argument and check, whether they are src_scheme[:exports code]{member?} of the second argument. Inside src_scheme[:exports code]{intersect-inner} the conditional never asks any questions about the second argument. It only ever asks things about the first argument. So the implementation cannot detect, that it is doing unnecessary work. Ideally we would not do any unnecessary work, of course.

We can easily add a check for an empty list as second argument:

#+NAME: intersect-def-2
#+begin_src scheme :noweb strip-export :results output replace drawer :wrap example :exports code :eval never-export :language guile
(define intersect
  (λ (set1 set2)
    (letrec ([member?
              (λ (elem lst)
                (member elem lst))]
             [intersect-inner
              (λ (set1°)
                (cond
                 [(null? set1°) '()]
                 [(member? (car set1°) set2)
                  (cons (car set1°)
                        (intersect-inner (cdr set1°)))]
                 [else
                  (intersect-inner (cdr set1°))]))])
      ;; added conditional
      (cond
       [(null? set2) '()]
       [else
        ;; still same call to intersect-inner
        (intersect-inner set1)]))))
#+end_src

Lets try it. Define src_scheme[:exports code]{intersectall} in terms of the new src_scheme[:exports code]{intersect}:

#+NAME: intersectall-def-4
#+begin_src scheme :noweb yes :results output replace drawer :wrap example :exports code :eval never-export :language guile
<<intersect-def-2>>


(define intersectall
  (λ (lsts)
    (call-with-current-continuation
     (λ (exit)
       (letrec ([intersectall-inner
                 (λ (lsts°)
                   (cond
                    [(null? (car lsts°)) (exit '())]  ; exit continuation call
                    [(null? (cdr lsts°)) (car lsts°)]
                    [else
                     (intersect (car lsts°)
                                (intersectall-inner (cdr lsts°)))]))])
         (cond
          [(null? lsts) '()]
          [else
           (intersectall-inner lsts)]))))))
#+end_src

~intersectall-inner~ can be used just like before.

#+NAME: intersectall-usage-4
#+begin_src scheme :noweb strip-export :results output replace drawer :wrap example :exports both :eval never-export :language guile
<<intersectall-def-4>>
(simple-format
 #t "~a\n"
 (intersect '(a b c) '(c d e)))


(simple-format
 #t "~a\n"
 (intersectall '((a b c)
                 (c d e)
                 (f c))))

(simple-format
 #t "~a\n"
 (intersectall '((a b c)
                 (c d e)
                 ()
                 (f g c))))
#+end_src

#+RESULTS: intersectall-usage-4
#+begin_example
(c)
(c)
()
#+end_example

That is nice. However we are not checking in src_scheme[:exports code]{intersectall}, whether src_scheme[:exports code]{intersect} gives an empty list as a return value, which will be the return value of src_scheme[:exports code]{intersectall} and so we might call src_scheme[:exports code]{intersect} unnecessarily with an empty list as second argument in iterations further up the stack. Instead, we could check for the result being the empty list. However, then we would check the same fact twice: Once inside src_scheme[:exports code]{intersect} and then again when src_scheme[:exports code]{intersect} returns in src_scheme[:exports code]{intersectall}. Again unnecessary work.

What we could do instead, is to let src_scheme[:exports code]{intersect} use the continuation created in src_scheme[:exports code]{intersectall}, once src_scheme[:exports code]{intersect} finds, that one of its arguments is an empty list.

There are at least 2 ways we can do this:

1. passing the continuation[fn:: Uh oh! Continuation Passing Style lurking!] to src_scheme[:exports code]{intersect}
2. moving src_scheme[:exports code]{intersect} into src_scheme[:exports code]{intersectall}, so that the continuation is accessible for src_scheme[:exports code]{intersect}

Option 1 is maybe not so great, since it requires src_scheme[:exports code]{intersect} to have an additional argument, which the caller might need to be aware of, or use optional arguments.

Option 2 is used in the book, but it also comes with a problem: src_scheme[:exports code]{intersect} is a useful function in itself. Moving it into src_scheme[:exports code]{intersectall} will make it impossible to use merely src_scheme[:exports code]{intersect}, instead of src_scheme[:exports code]{intersectall}. It will also make it impossible to write a unit test for src_scheme[:exports code]{intersect}. Perhaps the idea of the book is to simply always use src_scheme[:exports code]{intersectall} and wrap 2 arguments in a list, if one only needs the intersection of 2 sets. Or the idea is merely to have a case to show what continuations are and how they can be used to great effect.

So lets roll with option 2:

#+NAME: intersectall-def-5
#+begin_src scheme :noweb strip-export :results output replace drawer :wrap example :exports code :eval never-export :language guile
(define intersectall
  (λ (lsts)
    (call-with-current-continuation
     (λ (exit)
       (letrec ([intersect
                 ;; added internal definition of intersect
                 (λ (set1 set2)
                   (letrec ([member?
                             (λ (elem lst)
                               (member elem lst))]
                            [intersect-inner
                             (λ (set1°)
                               (cond
                                [(null? set1°) '()]
                                [(member? (car set1°) set2)
                                 (cons (car set1°)
                                       (intersect-inner (cdr set1°)))]
                                [else
                                 (intersect-inner (cdr set1°))]))])
                     (cond
                      ;; now calling the exit continuation
                      [(null? set2) (exit '())]
                      [else
                       (intersect-inner set1)])))]
                [intersectall-inner
                 (λ (lsts°)
                   (cond
                    [(null? (car lsts°)) (exit '())]
                    [(null? (cdr lsts°)) (car lsts°)]
                    [else
                     (intersect (car lsts°)
                                (intersectall-inner (cdr lsts°)))]))])
         (cond
          [(null? lsts) '()]
          [else
           (intersectall-inner lsts)]))))))
#+end_src

Lets try it:

#+NAME: intersectall-usage-5
#+begin_src scheme :noweb strip-export :results output replace drawer :wrap example :exports both :eval never-export :language guile
<<intersectall-def-5>>
(simple-format
 #t "~a\n"
 (intersectall '((a b c)
                 (c d e)
                 (f c))))

(simple-format
 #t "~a\n"
 (intersectall '((a b c)
                 (c d e)
                 ()
                 (f g c))))
#+end_src

#+RESULTS: intersectall-usage-5
#+begin_example
(c)
()
#+end_example

Still works!

** Example :: Skipping computation
:PROPERTIES:
:CUSTOM_ID: chapter-13-example-skipping
:END:

Another example for how continuations can be useful is skipping of computation or restarting computation with different state and thereby intentionally forgetting computation, that happened after the continuation was created. The example used in the book is the removal of all elements of a list up to and including the last occurrence of an element, that satisfies some predicate. The problem is, that in only 1 linear pass through the list, one does not know, whether one is removing too much of the list, because no later occurrence of such an element exists.

Here is a more flexible version of the code in the book, which also makes the predicate specifiable:

#+NAME: rember-up-to-last-def
#+begin_src scheme :noweb yes :results output replace drawer :wrap example :exports code :eval never-export :language guile
(define rember-up-to-last
  (λ (lst pred)
    (call-with-current-continuation
     (λ (restart)
       (letrec ([rember-inner
                 (λ (lst°)
                   (cond
                    [(null? lst°) '()]
                    [(pred (car lst°))
                     (restart (rember-inner (cdr lst°)))]
                    [else
                     (cons (car lst°)
                           (rember-inner (cdr lst°)))]))])
         (rember-inner lst))))))
#+end_src

We want to forget, what we accumulated in the src_scheme[:exports code]{else} branch, if we find another predicate satisfying list element. For that we use the continuation named src_scheme[:exports code]{restart}. We restart the accumulation of the result by using src_scheme[:exports code]{(rember-inner (cdr lst°))} in place of previous stack frames, that memorized accumulating other elements into a result.

Lets use it:

#+NAME: rember-up-to-last-usage
#+begin_src scheme :noweb strip-export :results output replace drawer :wrap example :exports both :eval never-export :language guile
<<rember-up-to-last-def>>
(simple-format
 #t "~a\n"
 (rember-up-to-last '(8 5 6 0 3 4 9 3 1)
                    (λ (num) (even? num))))
#+end_src

#+RESULTS: rember-up-to-last-usage
#+begin_example
(9 3 1)
#+end_example

** Notes about continuations
:PROPERTIES:
:CUSTOM_ID: chapter-13-example-continuations-notes
:END:

*** Specific language implementations
:PROPERTIES:
:CUSTOM_ID: chapter-13-example-continuations-notes-languages-specifics
:END:

The implementation using continuations is conceptually neat. However, in practice one needs to look out for language implementation specifics. For example GNU Guile's documentation mentions:

#+begin_quote
Continuations are a powerful mechanism, and can be used to implement almost any sort of control structure, such as loops, coroutines, or exception handlers.

However the implementation of continuations in Guile is not as efficient as one might hope, because Guile is designed to cooperate with programs written in other languages, such as C, which do not know about continuations. Basically continuations are captured by a block copy of the stack, and resumed by copying back.

For this reason, continuations captured by call/cc should be used only when there is no other simple way to achieve the desired result, or when the elegance of the continuation mechanism outweighs the need for performance.

Escapes upwards from loops or nested functions are generally best handled with prompts (see Prompts). Coroutines can be efficiently implemented with cooperating threads (a thread holds a full program stack but doesn’t copy it around the way continuations do).

-- https://www.gnu.org/software/guile/manual/html_node/Continuations.html (2023-02-22)
#+end_quote

So in a specific Scheme dialect like GNU Guile, one should weigh the costs of the elegance of an implementation using continuations against desired performance and consider other concepts like exceptions and prompts.

*** Other languages
:PROPERTIES:
:CUSTOM_ID: chapter-13-example-continuations-notes-other-languages
:END:

Another language, that is so nice to offer continuations, is Standard ML. See [[https://www.smlnj.org/doc/SMLofNJ/pages/cont.html]].

*** Other concepts
:PROPERTIES:
:CUSTOM_ID: chapter-13-example-continuations-notes-other-concepts
:END:

This section discusses other language concepts, that one could employ to get the same result.

**** Return statement
:PROPERTIES:
:CUSTOM_ID: chapter-13-example-continuations-notes-other-concepts-return-statement
:END:

In many languages a ~return~ statement might be used to return early. However, this requires there to be a ~return~ /statement/ in the language. For functional languages having statements like ~return~ does not make much sense, because everything or almost everything is an expression. Furthermore a ~return~ keyword is unnecessary to have in the language, as we have shown by effectively creating our own exit function using a continuation. A ~return~ statement can be seen as clutter in a language's syntax definition. Even some languages which do not prioritize functional programming have opted to not have a ~return~ statement. See Rust for example.

Having all things be expressions has loads of advantages. Everything can be expected to return some value. Everything can be moved around in the code and placed in other places, without for example worrying about things like it being correct or incorrect syntax to use a conditional inside another expression. Expressions make code more flexible. When languages mix expressions and statements, it can mean a much more complicated language and grammar of the language's syntax in the end. Look for example at Python and its ~if~ constructs. It has many special cases and inline syntax, that needs to be explicitly added to the language's syntax. For languages which handle these things as expressions there is no surprise, that one can use conditionals wherever one wants to. There is simply nothing special about conditionals.

**** Exceptions
:PROPERTIES:
:CUSTOM_ID: chapter-13-example-continuations-notes-other-concepts-exceptions
:END:

If not a ~return~ statement, then maybe an exception could be used to the same result? It could, but exceptions are actually meant to be used for exceptional circumstances and not for regular control flow. Using them for regular control flow is usually making it harder to read the code. If an exception is raised, it should be caught somewhere else in the code. That is more code. Also an exception type needs to be defined or an appropriate one already needs to exist. Also note, that using continuations one can implement exceptions in ones language. Using a continuation is using a more fundamental building block, a more basic concept.

**** Prompts
:PROPERTIES:
:CUSTOM_ID: chapter-13-example-continuations-notes-other-concepts-prompts
:END:

I do not yet know enough about prompts and their semantics to judge, whether they are conceptually fitting for being used instead of continuations. Them being mentioned in the GNU Guile manual makes me hopeful though, that they are indeed an appropriate concept to use in place of continuations.
